백준 14428번
오늘 풀어본 문제는 백준의 14428번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
길이가 $N$ 인 수열 $A_1,\ A_2,\ \cdots,\ A_N$ 이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.
-
$1\ i\ v$ : $A_i$ 를 $v$ 로 바꾼다. $(1 \le i \le N,\ 1 \le v \le 109)$
-
$2\ i\ j$ : $A_i,\ A_i+1,\ \cdots,\ A_j$ 에서 크기가 가장 작은 값의 인덱스를 출력한다. 그러한 값이 여러개인 경우에는 인덱스가 작은 것을 출력한다. $(1 \le i \le j \le N,\ 1 \le v \le 109)$
수열의 인덱스는 $1$ 부터 시작한다.
입력
첫째 줄에 수열의 크기 $N$ 이 주어진다. $(1 \le N \le 100,000)$
둘째 줄에는 $A_1,\ A_2,\ \cdots,\ A_N$ 이 주어진다. $(1 \le A_i \le 109)$
셋째 줄에는 쿼리의 개수 $M$ 이 주어진다. $(1 \le M \le 100,000)$
넷째 줄부터 $M$ 개의 줄에는 쿼리가 주어진다.
출력
$2$ 번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.
풀이과정
1번째 시도
이번에도 전형적인 세그먼트 트리를 활용하는 문제였다. 두 구간의 최소값과 그 인덱스를 알고 있다고 할 때, 두 값중 더 작은 값을 합친 구간의 최솟값으로 삼고, 같다면 인덱스를 비교하여 더 작은 것으로 합친 구간의 최솟값과 그 인덱스를 설정하는 방식으로 해결할 수 있을 것이라고 생각하였다.
코드는 다음과 같이 작성하였다. 제출할 때는 헤더파일의 코드를 붙여넣어 제출하였다.
segment_tree.hpp
#ifndef __SEGMENT_TREE_HPP__
#define __SEGMENT_TREE_HPP__
#include <vector>
template <typename T>
class SegmentTree {
private:
std::vector<T> tree;
std::vector<T> arr;
size_t n;
void build(size_t idx, size_t left, size_t right) {
if (left == right) {
tree[idx] = arr[left];
return;
}
size_t mid = (left + right) / 2;
build(2 * idx, left, mid);
build(2 * idx + 1, mid + 1, right);
const T& leftValue = tree[2 * idx];
const T& rightValue = tree[2 * idx + 1];
tree[idx] = leftValue * rightValue;
}
void update(size_t index, const T& value, size_t node, size_t currentLeft, size_t currentRight) {
if (currentLeft <= index && index <= currentRight) {
if (currentLeft == currentRight) {
tree[node] = value;
}
else {
size_t mid = (currentLeft + currentRight) / 2;
update(index, value, 2 * node, currentLeft, mid);
update(index, value, 2 * node + 1, mid + 1, currentRight);
tree[node] = tree[2 * node] * tree[2 * node + 1];
}
}
}
const T query(size_t i, size_t j, size_t node, size_t currentLeft, size_t currentRight) {
if (j < currentLeft || currentRight < i) {
return static_cast<T>(1);
}
else if (i <= currentLeft && currentRight <= j) {
return tree[node];
}
else {
size_t mid = (currentLeft + currentRight) / 2;
const T leftValue = query(i, j, 2 * node, currentLeft, mid);
const T rightValue = query(i, j, 2 * node + 1, mid + 1, currentRight);
return leftValue * rightValue;
}
}
public:
SegmentTree(const std::vector<T>& a) : arr(a), n(a.size()) {
tree.resize(4 * n + 1);
build(1, 0, n - 1);
}
void update(size_t index, const T& value) {
update(index, value, 1, 0, n - 1);
arr[index] = value;
}
const T query(size_t i, size_t j) {
return query(i, j, 1, 0, n - 1);
}
};
#endif // !__SEGMENT_TREE_HPP__
main.hpp
#include <bits/extc++.h>
#include "segment_tree.hpp"
using namespace __gnu_pbds;
using namespace std;
using ll = long long int;
using ull = unsigned long long int;
using pll = pair<ll, ll>;
struct MyMonoid {
int value;
int index;
bool identity;
MyMonoid(int value=1, int index=100000, bool identity=true) : index(index), value(value), identity(identity) {}
MyMonoid operator*(const MyMonoid& other) const {
if (this->identity) {
return other;
}
else if (other.identity) {
return *this;
}
else {
MyMonoid result;
if (this->value < other.value) {
result.value = this->value;
result.index = this->index;
}
else if (this->value > other.value) {
result.value = other.value;
result.index = other.index;
}
else {
result.value = this->value;
result.index = min(this->index, other.index);
}
result.identity = false;
return result;
}
}
};
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<MyMonoid> A(N);
for (int i=0; i<N; i++) {
int temp;
cin >> temp;
A[i] = MyMonoid(temp, i, false);
}
SegmentTree<MyMonoid> segtree(A);
int M;
cin >> M;
for (int m=0; m<M; m++) {
int q, i, j;
cin >> q >> i >> j;
if (q == 1) {
segtree.update(i-1, MyMonoid(j, i-1, false));
}
else {
cout << segtree.query(i-1, j-1).index + 1 << '\n';
}
}
return 0;
}
그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.
마무리
세그먼트 트리 하나 잘 만들어 놓으니 이 문제를 포함한 몇몇 문제는 굉장히 수월하게 풀리는 것 같다. 그런데 이제 그런 시절은 오늘이 마지막인 것 같다… 세그먼트 트리를 활용하는 다른 CLASS 6 문제들을 잠깐 살펴봤는데, 모노이드를 설계하는게 하나같이 전부 까다로워 보였다. 이것들도 구현하고 나면 쉬웠다고 느끼게 되는 걸까? 결국 풀어보는 수 밖에 없겠다.
내가 만든 세그먼트 트리 자료구조는 내 레포지토리2에서 확인할 수 있다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/14428
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/custom_data_structures/segment_tree.hpp